
import java.util.*;
import java.util.stream.Collectors;

public class HfTreeMain {

    public static Map<String, String> hfTableMap = new HashMap<>();
    // 生成赫夫曼树
    public static  HfTreeNode hfTreeStatic ;
    public static void main(String[] args) {
         final String string = "i love you you";
//        final String string = "uuuuugggfffcccbbbnnnnnnneeeeeeeeeeeeerrrrrrrrppppllk-ttttttttooooooooossssssssshhhhhmmmmmdddddiiiiiaaaaaaaaaa+++++++++++++++++++++++";
        final String stringabc = "abbb";
        // 获取队列，最后
        List<HfQueueNode> hfQueue = getHfQueue(string);

        // 获取赫夫曼编码表
        StringBuffer stringBuffer = new StringBuffer();
        hfTreeStatic = getHfTree(hfQueue);
        getHfCode(hfTreeStatic, stringBuffer);
        // 编码
        String encode = encode(hfTableMap, string);
        System.out.println(encode);
        char[] chars = "1011011010001001100001111001100111100110".toCharArray();
        decode(hfTreeStatic, chars,0);

    }

    /**
     * 解码
     *
     * @param hfTree
     * @param chars
     * @return
     */
    private static void decode(HfTreeNode hfTree, char[] chars, int index) {

        /**
         * 当前是子节点，包含数据
         */
        if (hfTree.isData()) {
            System.out.print(hfTree.getData());
            /**
             * 解码完成
             */
            if (index == chars.length){
                return;
            }else {
                /**
                 * 继续解码，从根节点开始遍历
                 */
                decode(hfTreeStatic, chars, index);
            }
        }else {
            /**
             * 指针后移，依据编码是0或者1决定解子节点或者右节点
             */
            index++;
            if (chars[index] == '0'){
                decode(hfTree.getLeftNode(),chars,index);
            }else {
                decode(hfTree.getRightNode(),chars,index);
            }

        }
    }

    /**
     * 编码
     *
     * @param hfTableMap
     * @param string
     * @return
     */
    private static String encode(Map<String, String> hfTableMap, String string) {
        StringBuffer code = new StringBuffer();
        for (char c : string.toCharArray()) {
            code.append(hfTableMap.get(String.valueOf(c)));
        }

        return code.toString();
    }

    /**
     * 获取哈夫曼编码，具有左子树，节编码+0，右子树节点编码+1
     * @param hfTree
     * @param sb
     */
    private static void getHfCode(HfTreeNode hfTree, StringBuffer sb) {
        if (hfTree == null) {
            return;
        } else {
            StringBuffer leftNode = new StringBuffer();
            getHfCode(hfTree.getLeftNode(), leftNode.append(sb).append(0));
            if (hfTree.isData()) {
                hfTableMap.put(hfTree.getData(), sb.toString());
            }
            StringBuffer rightNode = new StringBuffer();
            getHfCode(hfTree.getRightNode(), rightNode.append(sb).append(1));
        }
    }

    private static List<HfQueueNode> getHfQueue(String string) {
        List<HfQueueNode> hfQueueNodes = new LinkedList<>();

        /**
         * 编码字符加入map
         */
        char[] chars = string.toCharArray();
        Map<String, Integer> charCountMap = new LinkedHashMap<>();
        for (char aChar : chars) {
            Integer charCount = charCountMap.get(String.valueOf(aChar));
            if (charCount == null) {
                charCountMap.put(String.valueOf(aChar), 1);
            } else {
                charCountMap.put(String.valueOf(aChar), ++charCount);
            }
        }
        // 队列列表
        /**
         * 遍历Map加入队列
         */
        List<HfQueueNode> hfTreeNodes = new LinkedList<>();
        charCountMap.forEach((k, v) -> {
            HfQueueNode hfQueueNode = new HfQueueNode();
            hfQueueNode.setData(k);
            hfQueueNode.setCount(v);
            hfQueueNode.setIsData(true);
            hfTreeNodes.add(hfQueueNode);
        });

        /**
         * 顺序由次数 高到低排列
         */
        List<HfQueueNode> collect = hfTreeNodes.stream().sorted(Comparator.comparingInt(HfQueueNode::getCount).reversed()).collect(Collectors.toList());
        addHfQueueNode(collect, hfQueueNodes);
        return hfQueueNodes;

    }

    private static HfTreeNode getHfTree(List<HfQueueNode> hfQueue) {
        HfQueueNode remove = hfQueue.remove(hfQueue.size() - 1);
        List<List<HfQueueNode>> lists = new ArrayList<>();
        LinkedList<HfQueueNode> hfQueueNodes = new LinkedList<>();
        hfQueueNodes.add(remove);

        lists.add(hfQueueNodes);
        List<List<HfQueueNode>> hfQueueLists = getHfQueueLists(hfQueue, lists);


        List<List<HfTreeNode>> treeLists = new ArrayList<>();


        hfQueueLists.stream().forEach(item1 -> {
            LinkedList<HfTreeNode> hfTreeNodes = new LinkedList<>();

            item1.forEach(item2 -> {
                HfTreeNode hfTreeNode = new HfTreeNode();
                hfTreeNode.setData(item2.getData());
                hfTreeNode.setData(item2.isData());
                hfTreeNode.setCount(item2.getCount());
                hfTreeNodes.add(hfTreeNode);
            });
            treeLists.add(hfTreeNodes);
        });

        List<HfTreeNode> trrNode = createTreeNode(treeLists.remove(treeLists.size() - 1), treeLists.remove(treeLists.size() - 1), treeLists);

        return trrNode.get(0);
    }

    /**
     * 创建树节点node
     * @param lastFirst
     * @param lastSecond
     * @param treeLists
     * @return
     */
    private static List<HfTreeNode> createTreeNode(List<HfTreeNode> lastFirst, List<HfTreeNode> lastSecond, List<List<HfTreeNode>> treeLists) {
        lastSecond.forEach(item1 -> {
            if (!item1.isData()) {
                HfTreeNode rightNode = lastFirst.remove(0);
                HfTreeNode leftNode = lastFirst.remove(0);
                item1.setLeftNode(leftNode);
                item1.setRightNode(rightNode);
            }
        });
        if (treeLists.size() >= 1) {
            return createTreeNode(lastSecond, treeLists.remove(treeLists.size() - 1), treeLists);
        } else {
            return lastSecond;
        }
    }


    private static List<List<HfQueueNode>> getHfQueueLists(List<HfQueueNode> hfQueue, List<List<HfQueueNode>> lists) {
        long nextCount = lists.get(lists.size() - 1).stream().filter(item -> !item.isData()).count() * 2;

        LinkedList<HfQueueNode> hfQueueNodes = new LinkedList<>();

        for (int i = 0; i < nextCount; i++) {
            hfQueueNodes.add(hfQueue.remove(hfQueue.size() - 1));
        }
        lists.add(hfQueueNodes);

        if (hfQueue.size() > 0) {
            getHfQueueLists(hfQueue, lists);
        }
        return lists;

    }

    /**
     * 添加队列
     *
     * @param hfQueueNodes
     * @return
     */
    public static List<HfQueueNode> addHfQueueNode(List<HfQueueNode> hfQueueNodes, List<HfQueueNode> finalQueue) {
        if (hfQueueNodes.size() == 1) {
            HfQueueNode rootNode = new HfQueueNode();
            rootNode.setIsData(false);
            rootNode.setData(String.valueOf(hfQueueNodes.get(0).getCount() + hfQueueNodes.get(0).getCount()));
            rootNode.setCount(hfQueueNodes.get(0).getCount() + hfQueueNodes.get(0).getCount());
            finalQueue.addAll(hfQueueNodes);
            // finalQueue.add(rootNode);
            return finalQueue;
        } else {
            HfQueueNode latestFirstNode = hfQueueNodes.remove(hfQueueNodes.size() - 1);
            HfQueueNode latestSecondNode = hfQueueNodes.remove(hfQueueNodes.size() - 1);
            finalQueue.add(latestFirstNode);
            finalQueue.add(latestSecondNode);

            HfQueueNode sumNode = new HfQueueNode();
            sumNode.setIsData(false);
            int count = latestFirstNode.getCount() + latestSecondNode.getCount();
            sumNode.setCount(count);
            /**
             * 以最新的次数记录为数据
             */
            sumNode.setData(String.valueOf(count));
            hfQueueNodes.add(sumNode);
            // 重新排序
            List<HfQueueNode> sortQueueNodes = hfQueueNodes.stream().sorted(Comparator.comparingInt(HfQueueNode::getCount).reversed()).collect(Collectors.toList());
            addHfQueueNode(sortQueueNodes, finalQueue);
            return finalQueue;
        }

    }

}
